package TreeTest;

import linked.NodeTest;

public class BinarySearchTree {
    private static class TreeNode {
        private static class Info {
            boolean isContainN1;    //true表示包含n1
            boolean isContainN2;    //true表示包含n2  如果一个节点处同时为真 则该节点为最低父节点
            TreeNode findCom;   //最低公共祖先

            public Info(boolean n1, boolean n2,TreeNode findCom) {
                this.isContainN1 = n1;
                this.isContainN2 = n2;
                this.findCom=findCom;
            }
        }


        int value;
        TreeNode leftTree;
        TreeNode rightTree;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode leftTree, TreeNode rightTree) {
            this.value = val;
            this.leftTree = leftTree;
            this.rightTree = rightTree;
        }


        static class Dept{
            int minDept;

            public Dept(int minDept) {
                this.minDept = minDept;
            }
        }

        /**
         *
         * @param root TreeNode类
         * @return int整型
         * 求二叉树的最小深度
         */
        public int run (TreeNode root) {
            // write code here
            return getMinDept(root).minDept;
        }

        public static Dept getMinDept(TreeNode root){
            if (root == null){
                return new Dept(0);
            }
            if (root.leftTree==null || root.leftTree==null){
                return new Dept(0);
            }
            Dept leftDept=getMinDept(root.leftTree);
            Dept rightDept=getMinDept(root.rightTree);
            return new Dept((leftDept.minDept<rightDept.minDept?leftDept.minDept:rightDept.minDept)+1);
        }


        //二叉树的中序遍历
        public void midPrint(TreeNode treeNode){
            if (treeNode!=null){
                midPrint(treeNode.leftTree);
                System.out.print(treeNode.value);
                midPrint(treeNode.rightTree);
            }
        }

        /*
         * 求两个树节点的最低公共祖先
         * */


        //统计root根下（包括root根）是否发现t1  t2
        public static Info getLowCom(TreeNode root,TreeNode t1,TreeNode t2) {
            if (root == null) {
                return new Info(false, false,null);
            }
            Info leftInfo=getLowCom(root,t1,t2);     //左树上是否发现T1 T2  是否有发现最低公共祖先
            Info rightInfo=getLowCom(root,t1,t2);     //右树上是否发现T1 T2  是否有发现最低公共祖先
            if (leftInfo.findCom!=null){
                return new Info(true,true,leftInfo.findCom);
            }
            if (rightInfo.findCom!=null){
                return new Info(true,true,rightInfo.findCom);
            }

            //左右两树都没有发现最低公共祖先,但是刚好分别包含了t1和t2  也就是root成为公共祖先的条件
            if (leftInfo.isContainN1 && rightInfo.isContainN2){
                return new Info(true,true,root);
            }
            //左右两树都没有发现最低公共祖先,但是刚好分别包含了t1和t2  也就是root成为公共祖先的条件
            if (leftInfo.isContainN2 && rightInfo.isContainN1){
                return new Info(true,true,root);
            }

            boolean findt1= root==t1;
            boolean findt2= root==t2;
            //左右两树只发现了t1   root根是t2
            if (leftInfo.isContainN1 || rightInfo.isContainN1){
                if (findt2){
                    return new Info(true,true,root);
                }else {
                    return new Info(true,false,null);
                }
            }

            //左右两树只发现了t2   root根是t1
            if (leftInfo.isContainN2 || rightInfo.isContainN2){
                if (findt1){
                    return new Info(true,true,root);
                }else {
                    return new Info(false,true,null);
                }
            }

            //左右两树都没有发现t1  或者  t2
            return new Info(findt1,findt2,null);
        }
    }

}
